package com.tys.algorithm.advanced.test.class07;


import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.PriorityQueue;

/*
 * 手写加强堆
 * T一定要是非基础类型，有基础类型需要包一层
 */
public class HeapGreater<T> {
    private ArrayList<T> heap;
    private HashMap<T, Integer> indexMap;
    private int heapSize;
    private Comparator<? super T> comp;

    public HeapGreater(Comparator<? super T> c) {
        heap = new ArrayList<>();
        indexMap = new HashMap<>();
        heapSize = 0;
        comp = c;
    }

    public boolean isEmpty() {
        return heapSize == 0;
    }

    public int size() {
        return heapSize;
    }

    public boolean contains(T obj) {
        return indexMap.containsKey(obj);
    }

    public T peek() {
        return heap.get(0);
    }

    public void push(T obj) {
        heap.add(obj);
        indexMap.put(obj, heapSize);
        heapInsert(heapSize++);
    }

    public T pop() {
        T ans = heap.get(0);
        swap(0, heapSize - 1);
        indexMap.remove(ans);
        heap.remove(--heapSize);
        heapify(0);
        return ans;
    }

    public void remove(T obj) {
        T replace = heap.get(heapSize - 1);
        int index = indexMap.get(obj);
        indexMap.remove(obj);
        heap.remove(--heapSize);
        if (obj != replace) {
            heap.set(index, replace);
            indexMap.put(replace, index);
            resign(replace);
        }
    }

    public void resign(T obj) {
        heapInsert(indexMap.get(obj));
        heapify(indexMap.get(obj));
    }

    public List<T> getAllElements() {
        List<T> ans = new ArrayList<>();
        for (T c : heap) {
            ans.add(c);
        }
        return ans;
    }


    private void heapInsert(int index) {
        while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
            swap(index, (index - 1) / 2);
            index = (index - 1) / 2;
        }
    }

    private void heapify(int index) {
        int left = index * 2 + 1;
        while (left < heapSize) {
            int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
            best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
            if (best == index) {
                break;
            }
            swap(best, index);
            index = best;
            left = index * 2 + 1;
        }
    }


    private void swap(int i, int j) {
        T o1 = heap.get(i);
        T o2 = heap.get(j);
        heap.set(i, o2);
        heap.set(j, o1);
        indexMap.put(o2, i);
        indexMap.put(o1, j);

    }

    public static class MyComparator implements Comparator<Integer> {

        @Override
        public int compare(Integer o1, Integer o2) {
            return o1 - o2;
        }
    }

    public static void main(String[] args) {

        System.out.println("基本功能 test begin");
        int value = 1000;
        int testTimes = 1000000;
        HeapGreater<Integer> heap = new HeapGreater<>(new MyComparator());
        PriorityQueue<Integer> test = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < testTimes; i++) {
            int curValue = (int) (Math.random() * value);
            heap.push(curValue);
            test.add(curValue);
            if (Math.random() < 0.5) {
                if (!heap.isEmpty()) {
                    int heapPop = heap.peek();
                    int testPoll = test.peek();
                    if (heapPop != testPoll) {
                        System.out.println("Oops!");
                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
                        break;
                    }
//                    if(!(heap.pop().equals(test.poll()))){
//                        System.out.println("Oops!");
//                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
//                        break;
//                    }
                    heapPop = heap.pop();
                    testPoll = test.poll();
                    if (heapPop != testPoll) {
                        System.out.println("Oops!");
                        System.out.println("heapPop:" + heapPop + ", testPoll:" + testPoll);
                        break;
                    }
                }
            }
        }
        System.out.println("基本功能 test finish!");


        System.out.println("扩展方法 test begin");

        //加强
        int[] arr1 = {16, 12, 15, 8, 19, 13, 26, 37};
        //测试
        int[] arr2 = {16, 12, 15, 19, 13, 26, 37};
        //加入加强堆
        HeapGreater<Integer> h1 = new HeapGreater<>(new MyComparator());
        for (int i = 0; i < arr1.length; i++) {
            h1.push(arr1[i]);
        }
        h1.remove(8);
        List<Integer> list = h1.getAllElements();
        for (Integer num : list) {
            System.out.print(num + ", ");
        }
        System.out.println();

        //测试堆
        PriorityQueue<Integer> t1 = new PriorityQueue<>(new MyComparator());
        for (int i = 0; i < arr2.length; i++) {
            t1.add(arr2[i]);
        }
        Iterator<Integer> iterator = t1.iterator();
        while (iterator.hasNext()) {
            System.out.print(iterator.next() + ", ");
        }
        System.out.println();

        if (h1.peek() == t1.peek()) {
            System.out.println("ok");
        } else {
            System.out.println("error");
        }
        System.out.println("扩展方法 test end");

    }
}
